L’analyse combinatoire regroupe des méthodes mathématiques de dénombrement, de comptage d’objets vérifiant des propriétés particulières. Par exemple, quel est le nombre de mains de 13 cartes comportant trois as dans un jeu de 52 ? Combien y-a-t- il de façons d’affecter dix invités à dix chaises autour d’une table ?
Son importance en probabilité et statistique est considérable. Nous introduisons ici les principales notions de façon progressive.
On considère 5 objets numérotés numérotées de 1 à 5 et 5 boîtes identifiées par A, B, C, D, et E . On peut ranger l’objet 1 dans une quelconque des 5 boîtes : il y a donc 5 façons possibles.
Une fois l’objet A rangé, il reste 4 boîtes vides, donc quatre façons possibles de ranger B. Il y a donc 5 x 4 = 20 façons posibles de ranger les objets 1 et 2.
Une fois les objets 1 et 2 rangés, il reste trois boîtes vides. Pour chaque rangement des objets 1 et 2, il y a donc 3 façons de ranger l’objet 3. D’où 5 x 4 x 3 façons de ranger les trois premiers objets.
On considère mainenant les trois premiers objets rangés. Il reste deux boîtes vides, et donc, il y a (5 x 4 x 3) x 2 façons de ranger 4 objets dans 5 boîtes.
Il ne reste plus qu’une boîte vide pour l’objet 5, et il a y a donc 5 x 4 x 3 x 2 x 1 = 120 façons de ranger 5 objets dans 5 boîtes.
Dans le cas général , le nombre de façons de ranger n objets dans n boîtes est égal à n x (n – 1) x (n – 2) … x 2 x 1. Ce nombre s’appelle la factorielle de n ou factoriel n. Il est noté n ! .
|
n ! = 1 x 2 x 3 x … x (n–1) x n |
(0 ! = 1 par convention ) |
Supposons maintenant que le nombre de boîtes soit égal à 13, et le nombre d’objets à 5. Le même raisonnement nous donne le nombre de façons de ranger les 5 objets dans 5 boîtes choisies parmi les 9 :
13 x 12 x 11 x 10 x 9 = 154 440
C’est le nombre
d’arrangements de 5 objets dans 10 boîtes.Dans le cas général de n boîtes et p
objets, le nombre d’arrangements est
noté Anp . On a :
|
Anp = (n – p + 1) x (n – p + 2) ( n – p+3) x … (n – 1) x n |
1) Montrer que (n+1) ! = n ! x (n+1)
2) Calculer les factorielles des nombres 2, 3, 4, 5 … jusqu’à ce que la calculatrice donne un résultat non entier.
3) Montrer les relations suivantes :
|
Anp =
n ! /(n – p) ! |
An+1p = Anp (n+1) / (n – p
+ 1) |
Anp–1 = Anp / (n – p +1) |
4)
Calculer A105, A115, A125,A124.
Nous allons chercher maintenant le nombre de façons de choisir 5 boîtes parmi 13. On ne considère pas d’ordre ici : les choix A, B, C, D, E ou B, C, A, F, E sont équivalents.
On sait que le nombre de façons de ranger 5 objets dans 13 boîtes est égal à A135. Cette démarche se décompose en deux :
1) on choisit 5 boîtes parmi les 13 : on note C135 le nombre de choix possibles.
2) Une fois ce choix effectué, on range les 5 objets dans les cinq boîtes. Il y a 5 ! rangements possibles.
Le nombre de façons de ranger 5 objets dans 13 boîtes est égal au produit des deux :
|
A135
= C135 x 5 ! |
On en déduit :
|
C135 = A135 / 5 ! |
Dans le cas général de n boîtes et de p objets , on a :
|
CnP
= Anp / p ! |
= n !/ [ p ! (n – p) !] |
1) Calculer C95, C96 et C93, C94
2) Montrer les relations suivantes :
Cnp = Cnn–p Cnp + Cnp+1
= Cn+1p+1
1) On considère un ensemble de 2 éléments :
E = {a, b}
Quels sont les sous-ensembles de E ? Combien sont-ils ?
2) On considère F = E È {c}. Quels sont les sous-ensembles de F ? Combien sont-ils ?
3) On considère le cas général :
E = {e1, e2, e3,
…, en}
Déduire de tout sous-ensemble de E deux sous-ensembles de F = E È {en+1}.
4) En déduire que le nombre de parties d’un ensemble comportant n éléments est égal à 2n.
5) En déduire la relation suivante :
|
2n = Cn0 + Cn1 + Cn2 + Cn3 + … + Cnn |
1) Quel est le nombre de façons de choisir 10 cartes parmi les 52 ?
2) Quel est le nombre de façons de choisir 3 as parmi les 4 ?
3) En déduire le nombre de façons de choisir 13 cartes parmi les 52 comportant 3 as .
4) Quel est le nombre de de façons de choisir 13 cartes parmi les 52 comportant 3 as et 2 rois ? De choisir 13 cartes parmi les 52 comportant 3 as et 8 trèfles ?